package com.gxc.linkedList;

import java.util.*;

/**
 * 你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
 *
 * 给定一个员工数组 employees，其中：
 *
 * employees[i].id 是第 i 个员工的 ID。
 * employees[i].importance 是第 i 个员工的重要度。
 * employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。
 * 给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。
 */
public class GetImportance {

    /**
     * 深度优先病例
     * 1、首次循环记录每个员工的重要度
     * 2、第二次循环统计员工和他下属的重要值
     * @param employees
     * @param id
     * @return
     */
    public int handle(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        Map<Integer, Integer> res = new HashMap<>();
        //首次循环
        for (int i = 0; i < employees.size(); i++) {
            Employee employee = employees.get(i);
            map.put(employee.id, employee);
            res.put(employee.id, employee.importance);
        }
        //第二次循环
        /*for (int i = 0; i < employees.size(); i++) {
            Employee employee = employees.get(i);
            int imp = recursion(employee, map);
            res.put(employee.id, imp);
        }

        return res.get(id);*/
        return recursion(map.get(id), map);
    }

    private int recursion(Employee employee, Map<Integer, Employee> map) {
        if (employee.subordinates.isEmpty()) return 0;

        int sum = 0;
        for (int i = 0; i < employee.subordinates.size(); i++) {
            Integer j = employee.subordinates.get(i);
            Employee e = map.get(j);
            sum += recursion(e, map);
        }
        return sum + employee.importance;
    }

    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }

    //深度优先
    class Solution {
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();

        public int getImportance(List<Employee> employees, int id) {
            for (Employee employee : employees) {
                map.put(employee.id, employee);
            }
            return dfs(id);
        }

        public int dfs(int id) {
            Employee employee = map.get(id);
            int total = employee.importance;
            List<Integer> subordinates = employee.subordinates;
            for (int subId : subordinates) {
                total += dfs(subId);
            }
            return total;
        }
    }

    //广度优先
    class Solution2 {
        public int getImportance(List<Employee> employees, int id) {
            Map<Integer, Employee> map = new HashMap<Integer, Employee>();
            for (Employee employee : employees) {
                map.put(employee.id, employee);
            }
            int total = 0;
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(id);
            while (!queue.isEmpty()) {
                int curId = queue.poll();
                Employee employee = map.get(curId);
                total += employee.importance;
                List<Integer> subordinates = employee.subordinates;
                for (int subId : subordinates) {
                    queue.offer(subId);
                }
            }
            return total;
        }
    }


}
